package xyz.xiaotugou.algorithm;

import java.util.Arrays;

/**
 * @author ysy
 * @version 1.0
 * @Title: 移动零
 *          给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序
 *                  1. 必须在原数组上操作，不能拷贝额外的数组。
 *                  2. 尽量减少操作次数
 * @Note <b>ProjectName:</b> Pre-research
 * <br><b>PackageName:</b> xyz.xiaotugou.algorithm
 * <br><b>ClassName:</b> MoveZero
 * <br><b>Date:</b> 2022/1/10 22:03
 */
public class MoveZero {


    /**
     * @Author ysy
     * @Description
     * @Date 2022/1/10 22:07
     * @Param
     * @return void
     **/

    public static void moveZero(int[] nums){
        for(int i = 0, j = 0; i < nums.length; i++){
            if(nums[i] != 0) {
                nums[j] = nums[i];
                if(i != j) {
                    nums[i] = 0;
                }
                j++;
            }
        }
    }

    /**
     * @Author ysy
     * @Description 双指针：cursor每轮往前走，标记已移动的值；i标记新数组的索引，cursor对应值为0则i不动
     * @Date 2022/1/10 22:40
     * @Param 
     * @return void
     **/
    public static void moveZero1(int[] nums){
        for(int i = 0, cursor = 0; i < nums.length ; cursor++) {
            if(cursor >= nums.length){
                nums[i++] = 0;
            } else if(nums[cursor] != 0){
                nums[i++] = nums[cursor];
            }
        }
    }

    /**
     * @Author ysy
     * @Description 笨方法，两次处理，本质上还是两个指针
     * @Date 2022/1/10 22:49
     * @Param
     * @return void
     **/
    public static void moveZero2(int[] nums){
        int hook = 0;
        // 依次处理非0
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != 0){
                nums[hook++] = nums[i];
            }
        }
        // 遍历完，将锚点hook之后的值置为0
        for(int i = hook; i < nums.length; i++){
            nums[i] = 0;
        }
    }

    /**
     * @Author ysy
     * @Description 利用交换写法：j为新集合的索引[慢指针]，i为集合索引[快指针]
     * @Date 2022/1/10 22:57
     * @Param
     * @return void
     **/
    public static void moveZero3(int[] nums) {
        for(int i = 0, j = 0; i < nums.length; i++){
            if(nums[i] != 0){
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                j++;
            }
        }
    }

    public static void main(String[] args) {
        int[] num1 = {0,1,0,0,3,12,0};
        moveZero(num1);
        System.out.println(Arrays.toString(num1));

        int[] num2 = {0,1,0,0,3,12,0};
        moveZero1(num2);
        System.out.println(Arrays.toString(num2));

        int[] num3 = {0,1,0,0,3,12,0};
        moveZero1(num3);
        System.out.println(Arrays.toString(num3));

        int[] num4 = {0,1,0,0,3,12,0};
        moveZero1(num4);
        System.out.println(Arrays.toString(num4));
    }
}
